﻿#region Header

/*
Behavioral Rating of Dancing Human Crowds based on Motion Patterns
By

Pascal Hauser 
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

and

Raphael Gfeller
Dipl. Ing. in Informatik, Hochschule für Technik Rapperswil, 2006
Master Thesis, Hochschule für Technik Rapperswil, 2008-2010

*/

#endregion

#region Usings

using System;
using System.Drawing;

#endregion

namespace paravili.Algorithm {
	// ------------------------------------------------------------

	// This implementation correctly handles duplicate points, and
	// multiple points with the same x-coordinate.

	// 1. Sort the points lexicographically by increasing (x,y), thus 
	//    finding also a leftmost point L and a rightmost point R.
	// 2. Partition the point set into two lists, upper and lower, according as 
	//    point is above or below the segment LR.  The upper list begins with 
	//    L and ends with R; the lower list begins with R and ends with L.
	// 3. Traverse the point lists clockwise, eliminating all but the extreme
	//    points (thus eliminating also duplicate points).
	// 4. Eliminate L from lower and R from upper, if necessary.
	// 5. Join the point lists (in clockwise order) in an array.

	public class Convexhull {
		public static Point[] convexhull(Point[] pts) {
			// Sort points lexicographically by increasing (x, y)
			int N = pts.Length;
			if (N <= 1) {
				return pts;
			}
			Polysort.Quicksort(pts);
			Point left = pts[0];
			Point right = pts[N - 1];
			// Partition into lower hull and upper hull
			CDLL lower = new CDLL(left), upper = new CDLL(left);
			for (int i = 0; i < N; i++) {
				double det = Area2(left, right, pts[i]);
				if (det > 0) {
					upper = upper.Append(new CDLL(pts[i]));
				}
				else if (det < 0) {
					lower = lower.Prepend(new CDLL(pts[i]));
				}
			}
			lower = lower.Prepend(new CDLL(right));
			upper = upper.Append(new CDLL(right)).Next;
			// Eliminate points not on the hull
			eliminate(lower);
			eliminate(upper);
			// Eliminate duplicate endpoints
			if (lower.Prev.val.Equals(upper.val)) {
				lower.Prev.Delete();
			}
			if (upper.Prev.val.Equals(lower.val)) {
				upper.Prev.Delete();
			}
			// Join the lower and upper hull
			var res = new Point[lower.Size() + upper.Size()];
			lower.CopyInto(res, 0);
			upper.CopyInto(res, lower.Size());
			return res;
		}

		// Graham's scan
		private static void eliminate(CDLL start) {
			CDLL v = start, w = start.Prev;
			bool fwd = false;
			while (v.Next != start || !fwd) {
				if (v.Next == w) {
					fwd = true;
				}
				if (Area2(v.val, v.Next.val, v.Next.Next.val) < 0) // right turn
				{
					v = v.Next;
				}
				else {
					// left turn or straight
					v.Next.Delete();
					v = v.Prev;
				}
			}
		}

		public static double Area2(Point p0, Point p1, Point p2) {
			return p0.X * (p1.Y - p2.Y) + p1.X * (p2.Y - p0.Y) + p2.X * (p0.Y - p1.Y);
		}
	}

	//// ------------------------------------------------------------

	//// Points in the plane

	//public class Point : Point {
	//    private static readonly Random rnd = new Random();

	//    private double x, y;

	//    public int X {
	//        get {
	//            return (int)x;
	//        }
	//        set {
	//            x = (double)value;
	//        }
	//    }
	//    public int Y {
	//        get {
	//            return (int)y;
	//        }
	//        set {
	//            y = (double)value;
	//        }
	//    }

	//    public Point(double x, double y) {
	//        this.x = x; this.y = y;
	//    }

	//    public override string ToString() {
	//        return "(" + x + ", " + y + ")";
	//    }

	//    public bool Equals(Point p2) {
	//        return x == p2.x && y == p2.y;
	//    }

	//    public override bool Less(Point o2) {
	//        Point p2 = (Point)o2;
	//        return x < p2.x || x == p2.x && y < p2.y;
	//    }

	//    // Twice the signed area of the triangle (p0, p1, p2)
	//    public static double Area2(Point p0, Point p1, Point p2) {
	//        return p0.x * (p1.y - p2.y) + p1.x * (p2.y - p0.y) + p2.x * (p0.y - p1.y);
	//    }
	//}

	// ------------------------------------------------------------

	// Circular doubly linked lists of Point

	internal class CDLL {
		private CDLL next; // not null, except in deleted elements
		private CDLL prev; // not null, except in deleted elements
		public Point val;

		// A new CDLL node is a one-element circular list
		public CDLL(Point val) {
			this.val = val;
			next = prev = this;
		}

		public CDLL Prev {
			get { return prev; }
		}

		public CDLL Next {
			get { return next; }
		}

		// Delete: adjust the remaining elements, make this one point nowhere
		public void Delete() {
			next.prev = prev;
			prev.next = next;
			next = prev = null;
		}

		public CDLL Prepend(CDLL elt) {
			elt.next = this;
			elt.prev = prev;
			prev.next = elt;
			prev = elt;
			return elt;
		}

		public CDLL Append(CDLL elt) {
			elt.prev = this;
			elt.next = next;
			next.prev = elt;
			next = elt;
			return elt;
		}

		public int Size() {
			int count = 0;
			CDLL node = this;
			do {
				count++;
				node = node.next;
			} while (node != this);
			return count;
		}

		public void PrintFwd() {
			CDLL node = this;
			do {
				Console.WriteLine(node.val);
				node = node.next;
			} while (node != this);
			Console.WriteLine();
		}

		public void CopyInto(Point[] vals, int i) {
			CDLL node = this;
			do {
				vals[i++] = node.val; // still, implicit checkcasts at runtime 
				node = node.next;
			} while (node != this);
		}
	}

	// ------------------------------------------------------------

	internal class Polysort {
		private static void swap(Point[] arr, int s, int t) {
			Point tmp = arr[s];
			arr[s] = arr[t];
			arr[t] = tmp;
		}

		// Typed OO-style quicksort a la Hoare/Wirth

		private static void qsort(Point[] arr, int a, int b) {
			// sort arr[a..b]
			if (a < b) {
				int i = a, j = b;
				Point x = (arr[(i + j) / 2]);
				do {
					while (IsLess(arr[i], x)) {
						i++;
					}
					while (IsLess(x, arr[j])) {
						j--;
					}
					if (i <= j) {
						swap(arr, i, j);
						i++;
						j--;
					}
				} while (i <= j);
				qsort(arr, a, j);
				qsort(arr, i, b);
			}
		}

		public static bool IsLess(Point p1, Point p2) {
			return p1.X < p2.X || p1.X == p2.X && p1.Y < p2.Y;
		}

		public static void Quicksort(Point[] arr) {
			qsort(arr, 0, arr.Length - 1);
		}
	}
}